from collections import deque, namedtuple

class SemanticError(Exception):
    pass

class Symbol:
    def __init__(self, name, kind, typ, params=None, scope_path=None, value=None):
        self.name       = name           # 名称
        self.kind       = kind           # 'var' | 'func' | 'const'
        self.typ        = typ            # 'int', 'char *', ...
        self.params     = params or []   # 函数参数类型列表
        self.scope_path = scope_path     # 作用域路径
        self.value      = value          # 常量的字面值
        self.is_vararg  = False          # 是否为可变参数函数
        self.params      = params
        self.is_input_function = False   # 是否为输入函数（scanf）   

    def __repr__(self):
        p = f", params={self.params}" if self.params else ""
        v = f", value={self.value!r}" if self.kind=='const' else ""
        va = ", vararg" if self.is_vararg else ""
        return f"<Symbol {self.name}:{self.kind}:{self.typ}{p}{va} @{self.scope_path}>"

class SymbolTable:
    def __init__(self):
        self.scopes     = deque()
        self.history    = []    # (scope_path, dict) 列表，用于打印
        self._scope_id  = 0
        self.scope_path = []
        self.enter_scope()      # 全局作用域

    def enter_scope(self):
        self._scope_id += 1
        self.scope_path = self.scope_path + [self._scope_id]
        new_scope = {}
        self.scopes.append(new_scope)
        self.history.append((list(self.scope_path), new_scope))

    def leave_scope(self):
        self.scopes.pop()
        self.scope_path = self.scope_path[:-1]

    def declare(self, sym: Symbol):
        curr = self.scopes[-1]
        if sym.name in curr:
            raise SemanticError(f"重复声明: {sym.name} in scope {self.scope_path}")
        sym.scope_path = list(self.scope_path)
        curr[sym.name] = sym

    def lookup(self, name):
        for scope in reversed(self.scopes):
            if name in scope:
                return scope[name]
        return None

    def __repr__(self):
        # 收集
        consts = []
        strings = []
        vars_   = []
        funcs   = []
        for path, scope in self.history:
            sid = ";".join(map(str, path))
            for sym in scope.values():
                if sym.kind == 'const':
                    consts.append((sym.name, sym.typ, sym.value, sid))
                elif sym.kind == 'var':
                    vars_.append((sym.name, sym.typ, sid))
                elif sym.kind == 'func':
                    funcs.append((sym.name, sym.typ, len(sym.params), sym.params, sid))
                # string literal 已被当作 const(char*) 插入，若想单独分出：
                if sym.kind=='const' and sym.typ=='char *':
                    strings.append((sym.name, sym.value, sid))

        # 输出
        lines = []

        # 常量表
        lines.append("常量表：")
        lines.append(f"{'name':<6} {'type':<8} {'value':<12} {'scope'}")
        for n,t,v,s in consts:
            # 跳过字符串字面
            if t=='char *': continue
            lines.append(f"{n:<6} {t:<8} {repr(v):<12} {s}")
        lines.append("")

        # 字符串表
        lines.append("字符串表：")
        lines.append(f"{'name':<6} {'string':<20} {'scope'}")
        for n,val,s in strings:
            lines.append(f"{n:<6} {repr(val):<20} {s}")
        lines.append("")

        # 变量表
        lines.append("变量表：")
        lines.append(f"{'name':<6} {'type':<8} {'scope'}")
        for n,t,s in vars_:
            lines.append(f"{n:<6} {t:<8} {s}")
        lines.append("")

        # 函数表
        lines.append("函数表：")
        lines.append(f"{'name':<6} {'retType':<8} {'#params':<8} {'paramTypes':<15} {'scope'}")
        for n,rt,pn,pts,s in funcs:
            lines.append(f"{n:<6} {rt:<8} {pn:<8} {pts!s:<15} {s}")

        return "\n".join(lines)

class SemanticAnalyzer:
    def __init__(self, ast_root):
        self.root       = ast_root
        self.symtab     = SymbolTable()
        self.errors     = []
        self._const_seq = 0
        self._predefine_library_functions()

    def _predefine_library_functions(self):
        # printf(int)
                # printf 重载：既能打印数字也能打印字符串
        printf_sym = Symbol('printf', 'func', 'void')
        printf_sym.params = [['int'], ['char *']]  # 两种签名
        printf_sym.is_vararg = False
        self.symtab.declare(printf_sym)
        
        # scanf(int) — 读取数字
        # scanf 重载：读数字或读串
        scanf_sym = Symbol('scanf', 'func', 'void')
        scanf_sym.params = [['int'], ['char *']]  # 两种签名
        scanf_sym.is_input_function = True
        self.symtab.declare(scanf_sym)

    def error(self, msg):
        self.errors.append(msg)

    def _new_const(self, typ, literal):
        self._const_seq += 1
        name = f"C{self._const_seq}"
        val = literal + ('\0' if typ=='char *' else '')
        sym = Symbol(name, 'const', typ, scope_path=None, value=val)
        self.symtab.declare(sym)
        return typ

    def analyze(self):
        # 全局变量
        for d in self.root.children:
            if d.type == 'VarDecl':
                self.visit_VarDecl(d)
        # 函数
        for d in self.root.children:
            if d.type == 'FunDecl':
                self.visit_FunDecl(d)
        return self.symtab, self.errors

    def visit(self, node):
        method = getattr(self, f"visit_{node.type}", None)
        if method:
            return method(node)
        for c in node.children:
            self.visit(c)

    def visit_VarDecl(self, node):
        base = node.children[0].value
        for init in node.children[1:]:
            name = init.children[0].value
            vtype = 'char *' if len(init.children)==2 and init.children[1].type=='STRING' else base
            try:
                self.symtab.declare(Symbol(name, 'var', vtype))
            except SemanticError as e:
                self.error(str(e))
            if len(init.children)==2:
                child = init.children[1]
                t = self.visit(child)
                if t and t!=vtype:
                    self.error(f"初始化类型不匹配: {name} 为 {vtype}, 表达式为 {t}")

    def visit_FunDecl(self, node):
        rtype = node.children[0].value
        fname = node.children[1].value
        params= [p.children[0].value for p in node.children[2].children]
        try:
            self.symtab.declare(Symbol(fname, 'func', rtype, params=params))
        except SemanticError as e:
            self.error(str(e))
        self.symtab.enter_scope()
        for p in node.children[2].children:
            pname = p.children[1].value
            ptyp  = p.children[0].value
            try:
                self.symtab.declare(Symbol(pname, 'var', ptyp))
            except SemanticError as e:
                self.error(str(e))
        body = node.children[3]
        for local in body.children[0].children:
            self.visit_VarDecl(local)
        for stmt in body.children[1].children:
            self.visit(stmt)
        self.symtab.leave_scope()

    def visit_Assign(self, node):
        name = node.children[0].value
        sym  = self.symtab.lookup(name)
        if not sym:
            self.error(f"未声明变量: {name}")
            ltype=None
        else:
            ltype=sym.typ
        rtype = self.visit(node.children[1])
        if ltype and rtype and ltype!=rtype:
            self.error(f"赋值类型不匹配: {name} 为 {ltype}, 表达式为 {rtype}")
        return ltype

    def visit_ID(self, node):
        sym = self.symtab.lookup(node.value)
        if not sym:
            self.error(f"未声明标识符: {node.value}")
            return None
        return sym.typ

    def visit_NUM(self, node):
        return self._new_const('int', node.value)

    def visit_STRING(self, node):
        return self._new_const('char *', node.value)

    def visit_UnaryOp(self, node):
        return self.visit(node.children[0])

    def visit_BinaryOp(self, node):
        lt = self.visit(node.children[0])
        rt = self.visit(node.children[2])
        op = node.children[1].value
        if lt and rt and lt!=rt:
            self.error(f"操作数类型不一致: {lt}{op}{rt}")
            return None
        if op in ('&&','||','<','<=','>','>=','==','!='):
            return 'int'
        return lt

    def visit_Call(self, node):
        fname = node.value
        sym   = self.symtab.lookup(fname)
        if not sym or sym.kind!='func':
            self.error(f"未声明函数: {fname}")
            return None

        args = node.children[0].children
        # 先对每个实参做类型分析
        arg_types = [ self.visit(arg) for arg in args ]

        params = sym.params
        # 如果是 overload 列表（二维）
        if params and isinstance(params[0], list):
            # 在所有重载签名里找匹配
            for sig in params:
                if len(sig) == len(arg_types) and all(at==pt for at,pt in zip(arg_types, sig)):
                    return sym.typ
            # 如果走到这里，说明没有任何一个 overload 符合
            self.error(f"函数 {fname} 没有匹配重载: 调用参数类型 {arg_types} 不匹配任何 {params}")
            return sym.typ

        # 否则，按单一签名走旧逻辑
        if not sym.is_vararg and len(args)!=len(params):
            self.error(f"函数 {fname} 参数数目不匹配: 声明{len(params)}，调用{len(args)}")
        for i,(at,pt) in enumerate(zip(arg_types, params)):
            if at and pt and at!=pt:
                self.error(f"函数 {fname} 第{i+1} 参数类型不匹配: 要求{pt}，实际{at}")
        return sym.typ
def run_semantic_analysis(ast_root):
    analyzer = SemanticAnalyzer(ast_root)
    symtab, errors = analyzer.analyze()
    return symtab, errors